#include <bits/stdc++.h>
using namespace std;

/*
2536. 子矩阵元素加 1
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。

另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：

找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。
返回执行完所有操作后得到的矩阵 mat 。

 

示例 1：



输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]]
输出：[[1,1,0],[1,2,1],[0,1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。
- 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 
- 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。 
示例 2：



输入：n = 2, queries = [[0,0,1,1]]
输出：[[1,1],[1,1]]
解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 
- 第一个操作：将矩阵中的每个元素加 1 。
 

提示：

1 <= n <= 500
1 <= queries.length <= 104
0 <= row1i <= row2i < n
0 <= col1i <= col2i < n
*/

// 法一
class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        // 差分矩阵：1-based索引（避免边界判断），大小n+2适配首尾偏移
        vector<vector<int>> diff(n + 2, vector<int>(n + 2));

        // 处理每个查询：将子矩阵加1转化为差分矩阵4个点标记
        for (auto& q : queries) {
            int fx = q[0], fy = q[1], lx = q[2],
                ly = q[3]; // fx=起始行，fy=起始列，lx=结束行，ly=结束列
            diff[fx + 1][fy + 1]++; // 子矩阵左上角（1-based）+1
            diff[fx + 1][ly + 2]--; // 起始行+结束列右移，列方向终止标记
            diff[lx + 2][fy + 1]--; // 结束行下移+起始列，行方向终止标记
            diff[lx + 2][ly + 2]++; // 结束行下移+结束列右移，抵消重复减
        }

        // 一步前缀和（行列同时更新，容斥原理去重）：直接还原原矩阵
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; j++) {
                // 累加左列（列前缀）+ 上行（行前缀）- 左上重叠（容斥）
                diff[i][j] +=
                    diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1];
            }
        }

        // 裁剪多余行列（去掉n+2中首尾各1行/列，恢复n×n矩阵）
        diff.pop_back();          // 删最后一行
        diff.erase(diff.begin()); // 删第一行
        for (auto& row : diff) {
            row.pop_back();         // 删每行列尾
            row.erase(row.begin()); // 删每行列首
        }

        return diff; // 复用diff矩阵，避免额外空间开销
    }
};

// 法二
class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        // 二维差分矩阵   大小n+2避免边界越界
        vector<vector<int>> diff(n + 2, vector<int>(n + 2, 0));

        // 每个查询
        for (auto& q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            diff[r1][c1]++;         // 子矩阵左上角+1（起始位置）
            diff[r1][c2 + 1]--;     // 右上角右侧-1（列方向结束）
            diff[r2 + 1][c1]--;     // 左下角下方-1（行方向结束）
            diff[r2 + 1][c2 + 1]++; // 右下角对角+1（行列方向都结束，抵消重复减法）
        }
        // 每行做前缀和
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                diff[i][j] += diff[i][j - 1];
            }
        }
        // col
        for (int j = 0; j < n; ++j) {
            for (int i = 1; i < n; ++i) {
                diff[i][j] += diff[i - 1][j];
            }
        }

        // affect area n x n
        vector<vector<int>> res(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                res[i][j] = diff[i][j];
            }
        }
        return res;
    }
};